// 合并数组

const mergeArray = (arr1: Array<number>, arr2: Array<number>) => {
  // 缓存数组长度
  const len1 = arr1.length;
  const len2 = arr2.length;
  // 初始化两个指针
  let i = 0,
    j = 0;
  // 初始化结果数组
  const result: Array<number> = [];
  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }
  // 处理一方先遍历完的情况
  if (i < len1) {
    return result.concat(arr1.slice(i));
  } else {
    return result.concat(arr2.slice(j));
  }
};
// 归并排序
const mergeSort = (arr: Array<number>) => {
  // 处理边界条件
  if (!arr.length) return arr;
  // 缓存数组长度
  const len = arr.length;
  // 创建结果数组
  const result: Array<number> = [];
  // 计算分割点
  const mid = Math.floor(len / 2);
  // 递归分割左边分组,然后合并成有序数组
  const leftArr = mergeSort(arr.slice(0, mid));
  const rightArr = mergeSort(arr.slice(mid));
  // 合并左右两个数组
  arr = mergeArray(leftArr, rightArr);
  return arr;
};
